package progect_01;

import java.util.ArrayList;

public class TreeSort {
	public static void main(String[] args) {
		//二叉排序树--7, 3, 10, 12, 5, 1, 9
		int[] arr= {7, 3, 10, 12, 5, 1, 9};
		ArrayList<Node> list=new ArrayList<>();
		for(int i=0;i<arr.length;i++) {
			list.add(new Node(arr[i]));
		}
		BinarySortTree rooTree=new BinarySortTree(list.get(0));
		for(int i=1;i<list.size();i++) {
			rooTree.CreBinarySortTree(list.get(i));
		}
		//前序遍历
		rooTree.PreOrderPrint();
		
	}
	
}
class BinarySortTree{
	private Node rootNode;
	
	public BinarySortTree(Node rootNode) {
		this.rootNode=rootNode;
	}
	//前序遍历
	public void PreOrderPrint() {
		if(rootNode==null) {
			return;
		}else {
			rootNode.PreOrder();
		}
	}
	
	//创建二叉排序树
	public void CreBinarySortTree(Node node) {
		if(rootNode==null) {
			rootNode=node;
		}else {
			rootNode.add(node);
		}
		
	}
	
}
class Node{
	private int data;
	private Node leftNode;
	private Node rightNode;
	
	//前序遍历
	public void PreOrder() {
		System.out.print(this.getData()+" ");
		if(this.leftNode!=null) {
			this.leftNode.PreOrder();
		}
		if(this.rightNode!=null) {
			this.rightNode.PreOrder();
		}
		
	}
	
	
	//添加
	public void add(Node node) {
		//小的在左，大的在右，相同的随便放
		if(this.data>=node.data) {
			//要添加的结点应该放到左边
			if(this.leftNode!=null) {
				this.leftNode.add(node);
			}else {
				this.leftNode=node;
			}
		}else {
			//要添加的结点放到右边
			if(this.rightNode!=null) {
				this.rightNode.add(node);
			}else {
				this.rightNode=node;
			}
		}
		
		
	}
	
	//构造器
	public Node(int data) {
		this.data=data;
	}
	
	public void setData(int data) {
		this.data=data;
	}
	public int getData() {
		return data;
	}
	
	public void setLeft(Node leftNode) {
		this.leftNode=leftNode;
	}
	public Node getLeft() {
		return leftNode;
	}
	public void setRight(Node rightNode) {
		this.rightNode=rightNode;
	}
	public Node getRight() {
		return rightNode;
	}
	
}